显然,如果每次删一个点,答案可能会减小,而且你还不知道在哪里减小的...
所以我们反向思考,如果每次加一个点,那么答案肯定是不减的,而且如果答案变大,新矩阵一定包含该点。
表示以为起点出发向上能到达的 的个数。(遇到 停止)
表示以为起点出发向下能到达的 的个数。(遇到 停止)
都可以预处理,同时,我们也能用算出在所有点都无法选时(最后状态)的答案,记为,不知道的看一下这道题:P1387 最大正方形。
设当前加入的点为,首先,我们可以暴力更新,我们只需要知道当前区间最小的,如果小于它,就将 , 同时向两旁扩展一格(边长加1)显然我们可以用线段树维护。不用担心两旁遇到障碍的情况 , 这时的都为,无法对答案造成影响。
注意这里的线段树每次加点都要重建(在变)。
#include <cstdio>
#include <iostream>
using namespace std;
#define ls x << 1
#define rs x << 1 | 1
#define INF 0x3f3f3f3f
const int MAXN = 2000;
int n , m , k , Minu , Mind , Map[ MAXN + 5 ][ MAXN + 5 ];
int up[ MAXN + 5 ][ MAXN + 5 ] , down[ MAXN + 5 ][ MAXN + 5 ];
struct node{
int x , y , Ans;
}q[ MAXN + 5 ];
struct Point{
int l , r , minu , mind;
};
struct Segment_Tree{
Point Tree[ 4 * MAXN + 5 ];
void Pushup( int x ) {
Tree[ x ].minu = min( Tree[ ls ].minu , Tree[ rs ].minu );
Tree[ x ].mind = min( Tree[ ls ].mind , Tree[ rs ].mind );
}
void Build( int dex , int x , int l , int r ) {
Tree[ x ].l = l , Tree[ x ].r = r;
if( l == r ) {
Tree[ x ].minu = up[ dex ][ l ];
Tree[ x ].mind = down[ dex ][ l ];
return;
}
int Mid = ( l + r ) / 2;
Build( dex , ls , l , Mid );
Build( dex , rs , Mid + 1 , r );
Pushup( x );
}
void Find( int x , int l , int r ) {
if( r < Tree[ x ].l || Tree[ x ].r < l )
return;
if( l <= Tree[ x ].l && Tree[ x ].r <= r ) {
Minu = min( Minu , Tree[ x ].minu );
Mind = min( Mind , Tree[ x ].mind );
return;
}
Find( ls , l , r );
Find( rs , l , r );
}
}Tree;
int dp[ MAXN + 5 ][ MAXN + 5 ];
void Dp( ) {
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= m ; j ++ )
if( Map[ i ][ j ] ) {
dp[ i ][ j ] = min( dp[ i - 1 ][ j - 1 ] , min( dp[ i ][ j - 1 ] , dp[ i - 1 ][ j ] ) ) + 1;
q[ k ].Ans = max( q[ k ].Ans , dp[ i ][ j ] );
}
}
bool check( int x , int row ) {
if( x > n || x > m ) return 0;
for( int i = max( 1 , row - x + 1 ) ; i <= m - x + 1 ; i ++ ) {
Minu = Mind = INF; Tree.Find( 1 , i , i + x - 1 );
if( Minu + Mind - 1 >= x ) return 1;
}
return 0;
}
char s;
int main( ) {
scanf("%d %d %d",&n,&m,&k);
for( int i = 1 ; i <= n ; i ++ ) {
getchar( );
for( int j = 1 ; j <= m ; j ++ ) {
scanf("%c",&s);
Map[ i ][ j ] = ( s == '.' );
}
}
for( int i = 1 ; i <= k ; i ++ ) {
scanf("%d %d",&q[ i ].x,&q[ i ].y);
Map[ q[ i ].x ][ q[ i ].y ] = 0;
q[ i ].Ans = 0;
}
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= m ; j ++ )
up[ i ][ j ] = Map[ i ][ j ] ? up[ i - 1 ][ j ] + 1 : 0;
for( int i = n ; i >= 1 ; i -- )
for( int j = 1 ; j <= m ; j ++ )
down[ i ][ j ] = Map[ i ][ j ] ? down[ i + 1 ][ j ] + 1 : 0;
Dp( );
int Ans = q[ k ].Ans;
for( int i = k ; i >= 1 ; i -- ) {
int x = q[ i ].x , y = q[ i ].y; q[ i ].Ans = Ans;
Map[ x ][ y ] = 1;
up[ x ][ y ] = up[ x - 1 ][ y ] + 1;
for( int t = x + 1 ; t <= n && Map[ t ][ y ] ; t ++ )
up[ t ][ y ] += up[ x ][ y ];
down[ x ][ y ] = down[ x + 1 ][ y ] + 1;
for( int t = x - 1 ; t >= 1 && Map[ t ][ y ] ; t -- )
down[ t ][ y ] += down[ x ][ y ];
Tree.Build( x , 1 , 1 , m );
while( check( Ans + 1 , y ) ) Ans ++;
}
for( int i = 1 ; i <= k ; i ++ )
printf("%d\n",q[ i ].Ans);
return 0;
}